package ViolenceRecursive;

/**
 * @author Liaorun
 */
public class CardsInLine {

    /**
     * @param arr 所有的牌
     * @return 赢家的分数
     */
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        // 谁的分数打返回谁的分数
        return Math.max(f(arr, 0, arr.length - 1), f(arr, 0, arr.length - 1));
    }

    private static int f(int[] arr, int i, int j) {
        // 先手 base case:只有一张牌直接返回
        if (i == j) {
            return arr[i];
        }

        // 先手拿左右两张牌中大的那一张
        return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
    }

    private static int s(int[] arr, int i, int j) {
        // 后手 base case:只有一张牌拿不到牌
        if (i == j) {
            return 0;
        }

        // 后手拿到的是小排
        return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
    }
}
